const arr = [7, 5, 6, 8, 7, 7, 7, 2, 4, 1, 3]
// function quickSort (arr) {
//   if (arr.length <= 1) return arr
//   let pivotIndex = arr.length / 2 | 0
//   let pivot = arr.splice(pivotIndex, 1)[0]
//   let leftArr = []
//   let rightArr = []
//   for (let i = 0; i < arr.length; i++) {
//     pivot > arr[i] ? leftArr.push(arr[i]) : rightArr.push(arr[i])
//   }
//   return [...quickSort(leftArr), pivot, ...quickSort(rightArr)]
// }



// 快速排序
function quickSort (arr, left = 0, right = arr.length) {
  let partitionIndex
  if (left < right) {
    partitionIndex = partition(arr, left, right)
    quickSort(arr, left, partitionIndex - 1)
    quickSort(arr, partitionIndex + 1, right)
  }

  return arr
}
function partition (arr, left, right) {
  let pivot = left, index = left + 1;
  for (let i = index; i < right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index)
      index++
    }
  }
  swap(arr, pivot, index - 1)
  return index - 1
}

function swap (arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

let arr2 = quickSort(arr)
console.log(arr2, 99999999999)